package 中等.拓扑排序;

import java.util.*;

/**
 * 现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。
 * 给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi]
 * ，表示在选修课程 ai 前 必须 先选修 bi 。
 * 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。
 * 返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，
 * 你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。
 */
public class 课程表II_210 {

    public static void main(String[] args) {

    }

    /**
     * 拓扑排序+哈希表
     * 拓扑排序一层一层搜索，哈希表 key 表示课程，value 表示学习的顺序
     */
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] degree = new int[numCourses];
        List<Integer>[] lists = new List[numCourses];
        for (int i = 0; i < lists.length; i++) {
            lists[i] = new ArrayList<>();
        }
        for (int[] prerequisite : prerequisites) {
            int a = prerequisite[0], b = prerequisite[1];
            degree[a]++;
            lists[b].add(a);
        }
        int idx = 0;
        Map<Integer, Integer> map = new HashMap<>();
        Deque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < degree.length; i++) {
            if (degree[i] == 0) {
                queue.addLast(i);
            }
        }
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                Integer course = queue.pollFirst();
                map.putIfAbsent(course, idx++);
                for (Integer nextCourse : lists[course]) {
                    degree[nextCourse]--;
                    if (degree[nextCourse] == 0) {
                        queue.addLast(nextCourse);
                    }
                }
            }
        }

        if (map.size() < numCourses) {
            return new int[]{};
        }
        int[] ans = new int[numCourses];

        for (int i = 0; i < ans.length; i++) {
            ans[map.get(i)] = i;
        }
        return ans;
    }

}
